package org.example.day;

import java.util.ArrayDeque;
import java.util.Deque;

/**
 * @Description: TODO
 * @Author wyatt
 * @Data 2024/05/24 18:18
 */
//给你一个整数数组 nums 和一个正整数 k ，返回长度为 k 且最具 竞争力 的 nums 子序列。
//
//数组的子序列是从数组中删除一些元素（可能不删除元素）得到的序列。
//
//在子序列 a 和子序列 b 第一个不相同的位置上，如果 a 中的数字小于 b 中对应的数字，那么我们称子序列 a 比子序列 b（相同长度下）更具 竞争力 。 例如，[1,3,4] 比 [1,3,5] 更具竞争力，在第一个不相同的位置，也就是最后一个位置上， 4 小于 5 。
//
//
//
//示例 1：
//
//输入：nums = [3,5,2,6], k = 2
//输出：[2,6]
//解释：在所有可能的子序列集合 {[3,5], [3,2], [3,6], [5,2], [5,6], [2,6]} 中，[2,6] 最具竞争力。
//示例 2：
//
//输入：nums = [2,4,3,3,5,4,9,6], k = 4
//输出：[2,3,3,4]
//
//
//提示：
//
//1 <= nums.length <= 105
//0 <= nums[i] <= 109
//1 <= k <= nums.length
@Deprecated
public class Solution1673 {

    public static void main(String[] args) {
        Solution1673 solution1673 = new Solution1673();
        int[] nums = new int[]{2,4,3,3,5,4,9,6};
        int[] result = solution1673.mostCompetitive(nums , 4);
        for(int val : result){
            System.out.print(val + " ");
        }
    }

    public int[] mostCompetitive(int[] nums, int k) {

        int[] result = new int[k];

        int start = 0;
        for(int i=0;i<k;i++){
            int minIndex = getMin(nums, start, k - i);
            result[i] = nums[minIndex];
            start = minIndex + 1;
        }

        return result;
    }

    private int getMin(int[] nums, int start, int k) {

        int min = Integer.MAX_VALUE;
        int minIndex = start;
        for(int i = start; i<= nums.length - k; i++){
            if(nums[i] < min){
                min = nums[i];
                minIndex = i;
            }
        }

        return minIndex;
    }


    //    作者：力扣官方题解
    //    链接：https://leetcode.cn/problems/find-the-most-competitive-subsequence/solutions/2787293/zhao-chu-zui-ju-jing-zheng-li-de-zi-xu-l-27z4/
    //    来源：力扣（LeetCode）
    //    著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。
    public int[] mostCompetitive2(int[] nums, int k) {
        Deque<Integer> stack = new ArrayDeque<Integer>();
        int n = nums.length;
        for (int i = 0; i < n; i++) {
            while (!stack.isEmpty() && n - i + stack.size() > k && stack.peek() > nums[i]) {
                stack.pop();
            }
            stack.push(nums[i]);
        }
        int[] res = new int[k];
        while (stack.size() > k) {
            stack.pop();
        }
        for (int i = k - 1; i >= 0; i--) {
            res[i] = stack.pop();
        }
        return res;
    }



}
